package cn.suchan.jianzhi.q20_stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 知识点：包含min函数的栈
 * 题目描述
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
 *
 * @author suchan
 * @date 2019/05/27
 */
public class Solution {

    /**
     * 数据栈
     */
    private Stack<Integer> stack = new Stack();
    /**
     * 辅助栈
     */
    private Stack<Integer> minStack = new Stack<>();
    /**
     * 存放最小的元素
     */
    private Integer min = null;

    public void push(int node) {
        stack.push(node);

        if (minStack.empty()) {
            minStack.push(node);
            min = node;
        } else {
            if (node < min) {
                min = node;
                minStack.push(node);
            } else {
                minStack.push(min);
            }
        }
    }

    public void pop() {
        if (!stack.empty()) {
            stack.pop();
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.push(1);
        solution.push(-2);
        solution.push(3);
        solution.push(4);
        solution.push(5);

        System.out.println("top==>" + solution.top());
        System.out.println("min==>" + solution.min());
    }
}
